1. Field of the Invention
The present invention relates to logic circuits and, more particularly, to a method and apparatus for improving logic synthesis by fanout optimization.
2. Description of the Related Art
Logic circuits designs attempt to reduce a number of timing and capacitance violations. Fanout optimization is one method of achieving this reduction. Fanout optimization is the construction of a buffer tree to drive large capacitive loads so that timing and capacitance violations are reduced as much as possible. Fanout optimization is important in improving the performance of a logic circuit during logic synthesis but is one of the most time consuming synthesis transforms.
A proposed method of addressing the fanout problem is addressed in an article by K. J. Singh et al., "A Heuristic Algorithm for the Fanout Problem", pp. 357-360, Proc. of the 27th Design Automation Conference, 1990. The method described in this article relies on heuristics which assume some template topology for the buffer tree and then use some intelligent combinational search to select a buffer size for each tree node and a sink arrangement. These types of methods are polynomial in the number of sinks, the number of stages in the buffer tree and the number of buffers available in the library. As a result the runtime can be prohibitive when the number of sinks and the number of available buffers are large. The conventional approach typically builds a fanout tree based on the sizes and loads of buffers.
Therefore, a need exists for a fanout optimization method and apparatus for increasing the speed of logic synthesis. A further need exists for obtaining buffer sizes and a topology of a buffer tree while avoiding a combinational search by using an underlying delay model of the buffers. Yet another need exists for a method of reasoning with gain to build a fanout tree.